import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86131
 * Date: 2024-01-21
 * Time: 20:14
 */
public class TestHep {
    public int[] elem;  //一个数组
    public int usedSize;  //元素个数

    public TestHep(){
        this.elem = new int[10];
    }

    //初始化elem数组的
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //创建大根堆
    public void createBigHeap(){
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {  //从最下面开始循环
            siftDown(parent,usedSize);  //调节树的父亲结点是谁 ,还有结束结点是谁(变化的)
        }
    }

    private void siftDown(int parent,int end){
        int child = 2*parent+1;  //树的根节点以0为下标
        while(child < end){ //小于数组长度说明没调完
            if(child+1 < usedSize && elem[child] < elem[child+1]){ //child+1小于usedsize说明没有越界
                //判断左孩子如果比右孩子小的话,child就要指向右孩子,因为下一步要用最大的孩子结点和父亲结点交换
                child++;
            }
            //程序执行到这一步就说明child一定是左右孩子最大值的下标
            if(elem[child]>elem[parent]) {  //child和parent找出最大值进行交换
                //交换
                swap(child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;  //不用交换
            }
        }
    }

    private void swap(int i,int j){  //交换的方法
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //堆删除元素
    //1.将堆顶元素和堆中最后一个元素交换
    //2.将堆中有效数据个数减少一个
    //3.对堆顶元素进行向下调整
    public int poll(){
        int tmp = elem[0];
        swap(0,usedSize-1);  //堆顶元素和最后一个元素交换
        usedSize--;  //usedSize减一,元素还保留在数组,下次元素插入的时候直接覆盖
        siftDown(0,usedSize);  //最后一个元素在堆顶,直接向下调整堆顶元素即可
        return tmp;
    }

    //堆的插入
    public void offer(int val) {
        //1.判断数组满不满,满则扩容
        if(isFull()){
            //扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //2. 容量不满,可以插入元素
        elem[usedSize] = val;  //插入数组的最后
        usedSize++;

        //3.开始向上调整
        siftUp(usedSize-1);  //根节点从0开始,上一步加加,找到最后一个结点下标必须要元素个数减1
    }

    private void siftUp(int child) {
        int parent = (child - 1)/2; //根节点下标是0
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                //如果孩子结点比父亲结点大的话,就交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                //孩子结点要走到父亲节点位置,父亲结点也要向上走
                child = parent;
                parent = (child - 1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull() {
        return usedSize == elem.length;  //等于数组长度就说明满了
    }

    public void heapSort(){
        int end = usedSize-1;
        while(end > 0) {
            swap(0,end);
            siftDown(0,end-1);
            end--;
        }
    }
}
